[BZOJ1977]-次小生成树

最近公共祖先

传送门

题意：给定一张 $n$ 点 $m$ 边的无向图，求无向图的严格次小生成树的边权之和。

首先求出最小生成树的边权之和 $sum$。我们称最小生成树的 $n - 1$ 条边为树边，剩余 $m - n + 1$ 条边为非树边。

把一条非树边 $(x, y, z)$ 加入到最小生成树中，会与树上 $x$, $y$ 之间的路径形成一个环。设树上 $x$, $y$ 之间的路径上的最大边权为 $val1$，严格次大边权为 $val2$。

若 $z > val1$, 则把 $val1$ 对应的那条边替换成 $(x, y, z)$ 这条边，就得到了严格次小生成树的一个候选答案，边权之和为 $sum - val1 + z$ 。

若 $z = val1$, 则把 $val2$ 对应的那条边替换成 $(x, y, z)$ 这条边，就得到了严格次小生成树的一个候选答案，边权之和为 $sum - val2 + z$ 。

如上述枚举所有非树边，计算出所有候选答案，取最小值即为本题所求。

那么现在的问题就是：如何快速求出一条路径上的最大边权与严格次大边权。

可以用树上倍增算法来进行预处理。设 $F[x, k]$ 表示 $x$ 的 $2^k$ 祖先，$G[x, k, 0]$ 与 $G[x, k, 1]$ 分别表示 $x$ 到 $F[x, k]$ 的路径上的最大边权和严格次大边权。于是 $k \in [1, log N]$ 有：

如果 $G[x, k - 1, 0] \neq G[F[x, k - 1], k - 1, 0]$ ， 那么：

当 $k = 0$ 时，有初值：

接下来，我们考虑每条非树边 $(x, y, z)$ ，采用倍增 LCA 的框架，$x$、$y$ 每向上移动一段路径，就将该路径对应的最大边权和严格次大边权按照与求 $G$ 数组类似的方法合并到答案中。

$O(M log N)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
#define N 100010
#define M 300010
#define inf 0x7fffffff
using namespace std;

int n, m, o, minn = inf;
int to[M << 1], nxt[M << 1], val[M << 1], lnk[N], cnt;
int fa[N], d[N], f[N][20], G[N][20][2];
bool vis[M];
long long sum;
struct edge {
    int x, y, z;
}e[M];

void add(int x, int y, int z) {
    to[++cnt] = y, val[cnt] = z, nxt[cnt] = lnk[x], lnk[x] = cnt;
    to[++cnt] = x, val[cnt] = z, nxt[cnt] = lnk[y], lnk[y] = cnt;
}

int getfa(int w) {return fa[w] == w ? w : fa[w] = getfa(fa[w]);}

bool cmp(edge a, edge b) {return a.z < b.z;}

void kruskal() {
    sort(e + 1, e + m + 1, cmp);
    int num = 0;
    for (int i = 1; i <= m; i++) {
        int fx = getfa(e[i].x), fy = getfa(e[i].y);
        if (fx == fy) continue;
        fa[fx] = fy;
        sum += e[i].z;
        add(e[i].x, e[i].y, e[i].z);
        vis[i] = 1;
        num++;
        if (num == n - 1) break;
    }
}

void dfs(int x, int fa) {
    f[x][0] = fa;
    for (int i = lnk[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y != fa) {
            d[y] = d[x] + 1;
            G[y][0][0] = val[i];
            G[y][0][1] = -inf;
            dfs(y, x);
        }
    }
}

void beizeng() {
    for (int i = 1; i <= 18; i++)
        for (int j = 1; j <= n; j++) {
            f[j][i] = f[f[j][i - 1]][i - 1];
            G[j][i][0] = max(G[j][i - 1][0], G[f[j][i - 1]][i - 1][0]);
            G[j][i][1] = max(G[j][i - 1][1], G[f[j][i - 1]][i - 1][1]);
            if (G[j][i - 1][0] != G[f[j][i - 1]][i - 1][0])
                G[j][i][1] = max(G[j][i][1], min(G[f[j][i - 1]][i - 1][0], G[j][i - 1][0]));
        }
}

int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    int t = d[x] - d[y];
    for (int i = 0; i <= 18; i++)
        if ((1 << i) & t) x = f[x][i];
    if (x == y) return x;
    for (int i = 18; i >= 0; i--)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

void calc(int x, int xy, int v) {
    int mx1 = 0, mx2 = 0;
    int dis = d[x] - d[xy];
    for (int i = 0; i <= 20; i++) {
        if (dis & (1 << i)) {
            if (G[x][i][0] > mx1) mx2 = mx1, mx1 = G[x][i][0];
            mx2 = max(mx2, G[x][i][1]);
            x = f[x][i];
        }
    }
    if (mx1 != v) minn = min(minn, v - mx1);
    else
        minn = min(minn, v - mx2);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    }
    memset(vis, 0, sizeof(vis));
    kruskal();
    dfs(1, 0);
    beizeng();
    for (int i = 1; i <= m; i++) {
        if (vis[i] == 1) continue;
        int x = e[i].x, y = e[i].y, xy = lca(x, y);
        calc(x, xy, e[i].z), calc(y, xy, e[i].z);
    }
    printf("%lld\n", sum + minn);
    return 0;
}

唉，话说这篇代码真让我调得够呛。。。WA了六发不止。。。最后发现大概是计算 F 数组和 G 数组还有 beizeng() 预处理函数的问题，另外 lca 刚开头深度的比较与调换也错了。。。

不过！趁机学习了一发对拍～～～还是很有收获滴～～～

调试变难了不仅是错误百出的原因，还有最近图论不是很熟悉，因为图论本就是抽象的概念，但多做题一定会有所改善的！已经感觉到了= =